Given a non negative integer numbernum. For every numbersiin the range0 ≤ i ≤ numcalculate the number of 1's in their binary representation and return them as an array.

Example:
Fornum = 5you should return[0,1,1,2,1,2].

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)) . But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n) .
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Credits:
Special thanks to@ syedeefor adding this problem and creating all test cases.

class Solution {

public:

vector<int> countBits\(int num\) {

    vector<int> result\(num+1\);

    result\[0\]=0;

    if \(num==0\){

        return result;

    }

    int mark=2;

    result\[1\]=1;



    for \(int i=2;i<=num;i++\){

        if\(i<=\(2\*mark-1\)\){

            result\[i\]=result\[i-mark\]+1;

        }

        if\(i==\(2\*mark-1\)\){

           mark=2\*mark;

        }

    }



    return result;

}

};